Electronic circuits are often made up of gates or other circuit elements connected in networks. In some kinds of electronic circuits, multiple copies of gates or other circuit elements are typically implemented as integrated circuits and the overall electronic circuit consists of multiple integrated circuits assembled on one or more printed wiring boards. The connections among the integrated circuits are provided by wiring paths on the printed wiring boards. One typical electronic circuit of this kind uses devices called programmable gate arrays in which a relatively large number of gates is provided in an integrated circuit and the functions of and connections among the individual gates in the integrated circuit are specified by a "program." In some kinds of programmable gate arrays, the program is made part of the array during fabrication. In other kinds, known as field programmable gate arrays (FPGAs), the program is contained in a memory, such as a random-access or read-only memory associated with the array, or the program is "burned" into the array by electrically opening or closing fusible links.
In gate arrays and similar devices including multiple circuit elements, each gate or other circuit element can be thought of as a "cell" and the integrated circuits in which such gates are fabricated can be thought of as "blocks." In designing a circuit, a designer has the problem of partitioning the circuit by assigning the cells into blocks so that physical constraints, such as the number of cells in a block or the number of terminal pins on a block, are not violated. With programmable gate arrays, in which connections between cells can be made within a block, the choice of which cells in a circuit can be placed in a given block is often limited by the number of pins on the blocks. Blocks can also contain more than one type of cell, for example the Xilinx 4000 series FPGAs contain both configuration logic blocks and decoders. There may be other constraints to be imposed, such as limitations on types of cells or total power dissipated by cells.
The problem of partitioning a circuit into two or more blocks has received much attention. For example, see "A Linear-Time Heuristic for Improving Network Partitions" by C. M. Fiduccia and R. M. Mattheyses, Proc. of 19th IEEE Design Automation Conference, pp. 175-181, 1982; "An Improved Min-Cut Algorithm for Partitioning VLSI Networks" by Balakrishnan Krishnamurthy, IEEE Transactions on Computers, Vol. C-33, No. 5, pp. 438-446, 1984; and "Multiple-Way Network Partitioning" by Laura A. Sanchis in IEEE Transactions on Computers, Vol. 38, No. 1, pp. 62-81, 1989. However, the problems posed by pin limitations and multiple cell types in blocks remain.